export class Node {
    constructor(val = null, next = null) {
        this.val = val
        this.next = next
    }

}

export class LinkedList {
    constructor() {
        this.head = null
        this.dummyHead = new Node()
        this.size = 0
    }

    static arrayToLinkedList(arr) {
        const list = new LinkedList()

        for (let i = 0; i < arr.length; i++) {
            list.addLast(arr[i])
        }

        return list
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    add(index, e) { // O(n)
        if (index < 0 || index > this.size) {
            throw new Error('Add failed. Illegal index.')
        }

        let prev = this.dummyHead

        for (let i = 0; i < index; i++) {
            prev = prev.next
        }

        prev.next = new Node(e, prev.next)
        this.size++
    }

    addFirst(e) { // O(1)
        this.add(0, e)
    }

    addLast(e) { // O(n)
        this.add(this.size, e)
    }

    get(index) { // O(n)
        if (index < 0 || index > this.size) {
            throw new Error('Get failed. Illegal index.')
        }

        let cur = this.dummyHead.next
        for (let i = 0; i < index; i++) {
            cur = cur.next
        }

        return cur.val
    }

    getFirst() { // O(1)
        return this.get(0)
    }

    getLast() { // O(n)
        return this.get(this.size - 1)
    }

    set(index, e) { // O(n)
        if (index < 0 || index > this.size) {
            throw new Error('Get failed. Illegal index.')
        }

        let cur = this.dummyHead.next
        for (let i = 0; i < index; i++) {
            cur = cur.next
        }

        cur.val = e
    }

    contains(e) { // O(n)
        let cur = this.dummyHead.next

        while (cur !== null) {
            if (cur.val === e) {
                return true
            }
            cur = cur.next
        }

        return false
    }

    remove(index) { // O(n)
        if (index < 0 || index > this.size) {
            throw new Error('Remove failed. Illegal index.')
        }

        let prev = this.dummyHead

        for (let i = 0; i < index; i++) {
            prev = prev.next
        }

        const cur = prev.next
        prev.next = cur.next
        cur.next = null
        this.size--

        return cur
    }

    removeFirst() { // O(1)
        return this.remove(0)
    }

    removeLast() { // O(n)
        return this.remove(this.size - 1)
    }

    removeElement(e) {
        let prev = this.dummyHead
        while (prev.next !== null) {
            if (prev.next.val === e) {
                break
            }
            prev = prev.next
        }

        if (prev.next !== null) {
            const delNode = prev.next
            prev.next = delNode.next
            delNode.next = null
            this.size--
        }
    }

    toString() {
        const arr = []
        let cur = this.dummyHead.next
        while (cur !== null) {
            arr.push(cur.val)
            cur = cur.next
        }

        return arr.join('->')
    }

}